#include <algorithm>
using namespace std;
class Solution {
public:
    void sortColors(int A[], int n) {
        int h=0, t=n-1, w=-1;
        while (h<=t) {
            while (h<=t && A[h]==0) ++h;
            while (h<=t && A[t]==2) --t;
            if (h>t) break;
            if (A[h]!=1 || A[t]!=1)
                swap(A[h], A[t]);
            else {
                if (w==-1 || w<=h) w=h+1;
                while (w<t && A[w]==1) ++w;
                if (w>=t) break;
                if (A[w]==0)
                    swap(A[h], A[w]);
                else
                    swap(A[w], A[t]);
            }
        }
    }
};
